package nl.rug.jvleusen.datastructurelib.set;

import java.lang.reflect.Array;
import java.util.Collection;
import java.util.Iterator;
import java.util.NoSuchElementException;
import nl.rug.jvleusen.datastructurelib.ISet;

/**
 * The Multiset is defined as a set that can accept more than 1 of each element,
 * thus the implementation of various methods differ from the default
 * Collection, be aware that this class does not act like a normal collection.
 *
 * @author Jeroen van Leusen
 */
public class MultiSet<E> implements ISet<E> {

    private Bag<E>[] array;
    private int totalSize = 0;
    private int uniqueSize = 0;

    /**
     * Initializes the set with the default amount (16)
     */
    public MultiSet() {
        this(16);
    }

    /**
     * Initializes the set with the specified amount.
     *
     * @param size Initial size to allocate.
     */
    public MultiSet(int size) {
        array = new Bag[size];
    }

    /**
     * Initializes the set to the size of the specified collection and inserts
     * all elements of the specified collection
     *
     * @param c Collection to initialize from.
     */
    public MultiSet(Collection<? extends E> c) {
        this(c.size());
        addAll(c);
    }

    /**
     * The MultiSet union implementation differs from the usual implementation,
     * to compute it for each element of both sets, the count of said element is
     * taken and the max of those two values is set to be the value in the
     * union.
     *
     * @param set2 Set to compute the union with
     * @return union as defined by MultiSet set theory.
     */
    public ISet<E> union(ISet<E> set2) {
        MultiSet<E> set = new MultiSet<E>(this);
        for (E element : set2) {
            int index = set.indexFor(element);
            if (index == -1) {
                set.add(element, getCountSafe(set2, element));
            } else {
                Bag<E> bag = set.array[index];
                int newSize = Math.max(bag.count, getCountSafe(set2, element));
                set.totalSize += (newSize - bag.count);
                bag.count = newSize;
            }
        }
        return set;
    }

    /**
     * The MultiSet intersection implementation differs from the usual
     * implementation, to compute it the final set must contain the Minimum
     * amount of each element from both sets, so an element has to be in both
     * sets and the total amount is set to the {@link Math#min(int, int)} of the
     * {@link MultiSet#getCount(java.lang.Object)} of each set.
     *
     * @param set2 Set to compute the intersection with
     * @return intersection as defined by MultiSet set theory.
     */
    public ISet<E> intersection(ISet<E> set2) {
        MultiSet<E> set = new MultiSet<E>(this);
        for (Bag<E> bag : set.array) {
            int minimum = Math.min(bag.count, getCountSafe(set2, bag.content));
            if (minimum == 0) {
                set.remove(bag.content);
            } else if (minimum < bag.count) {
                set.totalSize -= (bag.count - minimum);
                bag.count = minimum;
            }
        }

        return set;
    }

    /**
     * This one uses this class' implementation of {@link MultiSet#union(nl.rug.jvleusen.datastructurelib.ISet)}
     * and {@link MultiSet#intersection(nl.rug.jvleusen.datastructurelib.ISet)}
     * to compute the difference according to the set definition, which is that
     * the difference is the union with the intersection removed.
     *
     * @param set2 Set to compute the difference with
     * @return difference as defined by MultiSet set theory.
     */
    public ISet<E> difference(ISet<E> set2) {
        MultiSet<E> unioned = (MultiSet<E>) union(set2);
        MultiSet<E> intersection = (MultiSet<E>) intersection(set2);

        //Now we need to remove everything that is in the intersection
        for (E element : intersection.uniqueSet()) {
            unioned.remove(element, intersection.getCount(element));
        }

        return unioned;
    }

    /**
     * Will return true if each element of set2 is in this set, if set2 is also
     * a multiset it will also check if the amount of said element in set2 is
     * equal or less than in this set, otherwise it is false anyway.
     *
     * To check whether this set contains each element regardless of count, use {@link MultiSet#containsAll(java.util.Collection)}
     *
     * @param set2 to check whether it is a subset.
     * @return Whether set2 is a subset of this set.
     */
    public boolean subset(ISet<E> set2) {
        for (E e : set2) {
            if (getCountSafe(set2, e) > getCount(e)) {
                return false;
            }
        }
        return true;
    }

    /**
     * In this implementation, this will return the amount of unique elements in
     * this MultiSet, to get the cardinality of this set use {@link MultiSet#totalSize()}
     *
     * @return Amount of unique elements in this set.
     */
    public int size() {
        return uniqueSize;
    }

    /**
     * Returns the cardinality of this set, to get the amount of unique elements
     * in this set use {@link MultiSet#size()}
     *
     * @return The cardinality of this set.
     */
    public int totalSize() {
        return totalSize;
    }


    /**
     * {@inheritDoc}
     */
    public boolean isEmpty() {
        return size() == 0;
    }


    /**
     * {@inheritDoc}
     */
    public boolean contains(Object o) {
        return indexFor(o) != -1;
    }

    /**
     * This method will create an iterator that will return each element {@link MultiSet#getCount(java.lang.Object)}
     * of said element times, to get an iterator that just returns each element
     * once, use {@code uniqueSet().iterator()}
     *
     * @return an Iterator for every single element in this set.
     */
    public Iterator<E> iterator() {
        return new BagIterator<E>();
    }

    /**
     * This will return an array containing all the elements of the multiset,
     * each element can appear more than once.
     *
     * @return An object array containing the full set of elements of this set.
     */
    public Object[] toArray() {
        Object[] result = new Object[totalSize];
        int cursor = 0;
        for (Bag<E> bag : array) {
            if (bag != null) {
                for (int i = 0; i < bag.count; i++) {
                    result[cursor++] = bag.content;
                }
            }
        }
        return result;
    }

    /**
     * This will attempt to return an array of the specified type containing
     * every single element of this set.
     *
     * @param <T> 
     * @param a Array signifying the type of the resulting array.
     * @return An array containing each element of this set.
     * @throws ArrayStoreException If the elements of this set do not cast to
     * the specified type.
     */
    public <T> T[] toArray(T[] a) {
        if (a.length < totalSize) {
            a = (T[]) Array.newInstance(a.getClass().getComponentType(), totalSize);
        }

        Object[] result = a;
        int cursor = 0;
        for (Bag<E> bag : array) {
            if (bag != null) {
                for (int i = 0; i < bag.count; i++) {
                    result[cursor++] = bag.content;
                }
            }
        }
        return a;
    }

    /**
     * Adds a single count of {@code e} to the set, this method is a violation
     * of the specification of {@link Collection}, and will always return true
     * since the set is always changed.
     *
     * @param e Element to increment within the set
     * @return Whether the set has changed as a result of this action (Always
     * true)
     * @throws NullPointerException If you try to add NULL
     */
    public boolean add(E e) {
        return add(e, 1);
    }

    /**
     * Adds the specified amount {@code count} of a certain item to the set, if
     * the item doesn't exist it is created with the specified amount, otherwise
     * the amount of said item is raised by the specified amount.
     *
     * @param e Element to increment.
     * @param count Number by which to increment the amount of element within
     * the set.
     * @return Whether the set has changed as a result of this action (Always
     * true)
     * @throws NullPointerException If you try to add NULL
     * @throws IllegalArgumentException If you enter an illegal amount as count,
     * for example zero or a negative number.
     */
    public boolean add(E e, int count) {
        if (count <= 0) {
            throw new IllegalArgumentException("Don't add nothing or negative to a multiset.");
        }

        if (e == null) {
            throw new NullPointerException("This implementation doesn't support NULL");
        }

        int index = indexFor(e);
        if (index == -1) {
            if (uniqueSize == array.length) {
                resize(2 * array.length);
            }
            index = 0;
            while (array[index] != null) {
                index++;
            }
            array[index] = new Bag<E>(e, count);
            uniqueSize++;
            totalSize += count;
        } else {
            array[index].count += count;
            totalSize += count;
        }
        return true;
    }

    /**
     * This method removes an element from the multiset, regardless of its
     * current count, after using this method {@code contains(o)} will return
     * false.
     *
     * @param o Object that should be removed.
     * @return Whether the set changed as a result of this action.
     */
    public boolean remove(Object o) {
        int index = indexFor(o);
        if (index == -1) {
            return false;
        } else {
            totalSize -= array[index].count;
            uniqueSize--;
            array[index] = null;
            return true;
        }
    }

    /**
     * Removes a specified count of an object from the set, you cannot remove
     * more than exists within the set and if the count of an element is reduced
     * to zero it will be removed.
     *
     * @param o Element to remove from
     * @param count Amount to remove from the specified element's count.
     * @return Whether the set changed as a result of this action.
     * @throws IllegalArgumentException If an illegal count is specified, like
     * zero or a negative amount.
     */
    public boolean remove(Object o, int count) {
        if (count <= 0) {
            throw new IllegalArgumentException("Don't remove nothing or negative from a multiset.");
        }

        int index = indexFor(o);
        if (index == -1) {
            return false;
        } else {
            Bag<E> bag = array[index];
            int newSize = bag.count - count;
            if (newSize <= 0) {
                totalSize -= bag.count;
                uniqueSize--;
                array[index] = null;
            } else {
                bag.count = newSize;
                totalSize -= count;
            }
            return true;
        }
    }

    /**
     * Returns whether each object of the specific collections appears at least
     * once within this set.
     *
     * @param c Collection to check elements of.
     * @return Whether each element of the collection occurs in this set.
     */
    public boolean containsAll(Collection<?> c) {
        for (Object o : c) {
            if (indexFor(o) == -1) {
                return false;
            }
        }
        return true;
    }

    /**
     * Calls {@link MultiSet#add(Object)} for each element within the specified
     * collection.
     *
     * @param c Collection to add to this set.
     * @return Whether this set changed as a result of this action.
     */
    public boolean addAll(Collection<? extends E> c) {
        boolean modified = false;
        for (E element : c) {
            if (element != null && add(element)) {
                modified = true;
            }
        }
        return modified;
    }

    /**
     * Calls {@link MultiSet#remove(java.lang.Object)} on each element of the
     * specified collection, this means that after this method no element that
     * exists within the specified collection will exist within this set.
     *
     * @param c Collection to compare with.
     * @return Whether the set changed as a result of this action.
     */
    public boolean removeAll(Collection<?> c) {
        boolean modified = false;
        for (Object o : c) {
            if (o != null && remove(o)) {
                modified = true;
            }
        }
        return modified;
    }

    /**
     * Removes all elements that are in this set but not in the specified
     * collection, after this method only elements that are also in the
     * specified collection are contained in this set.
     *
     * @param c Collection to compare with.
     * @return Whether the set changed as a result of this action.
     */
    public boolean retainAll(Collection<?> c) {
        boolean modified = false;
        for (Bag<E> bag : array) {
            if (bag != null) {
                if (!c.contains(bag.content)) {
                    remove(bag.content);
                }
            }
        }
        return modified;
    }


    /**
     * {@inheritDoc}
     */
    public void clear() {
        for (int i = 0; i < array.length; i++) {
            if (array[i] != null) {
                array[i] = null;
            }
        }
        array = new Bag[16];
        totalSize = 0;
        uniqueSize = 0;
    }

    /**
     * MultiSet-specified method that will return the count of each element, it
     * will return 0 is an element is not present.
     *
     * @param o Object to check for
     * @return The cardinality of the specified object.
     */
    public int getCount(Object o) {
        int index = indexFor(o);
        if (index == -1) {
            return 0;
        } else {
            return array[index].count;
        }
    }

    private int indexFor(Object o) {
        for (int i = 0; i < array.length; i++) {
            if (array[i] != null && array[i].content.equals(o)) {
                return i;
            }
        }
        return -1;
    }

    /**
     * Will return a {@link Set} containing one of each element in this set.
     *
     * @return A set containing one of each element within this set.
     */
    public Set<E> uniqueSet() {
        Set<E> unique = new Set<E>(uniqueSize);
        for (int i = 0; i < array.length; i++) {
            if (array[i] != null) {
                unique.add(array[i].content);
            }
        }
        return unique;
    }

    private static int getCountSafe(Collection<?> c, Object o) {
        if (c instanceof MultiSet) {
            return ((MultiSet) c).getCount(o);
        } else {
            return c.contains(o) ? 1 : 0;
        }
    }

    private void resize(int size) {
        Bag<E>[] newArray = (Bag<E>[]) new Bag[size];
        System.arraycopy(array, 0, newArray, 0, array.length);
        array = newArray;
    }

    private static class Bag<E> {

        private final E content;
        private int count;

        public Bag(E item, int count) {
            this.content = item;
            this.count = count;
        }
    }

    private class BagIterator<E> implements Iterator<E> {

        Iterator<E> uniqueIterator = (Iterator<E>) uniqueSet().iterator();
        int count = 0;
        E lastItem = null;

        public boolean hasNext() {
            return count > 0 || uniqueIterator.hasNext();
        }

        public E next() {
            if (count > 0) {
                count--;
                return lastItem;
            } else {
                if (!uniqueIterator.hasNext()) {
                    throw new NoSuchElementException();
                }
                lastItem = uniqueIterator.next();
                count = getCount(lastItem) - 1;
                return lastItem;
            }
        }

        public void remove() {
            if (lastItem != null) {
                MultiSet.this.remove(lastItem);
                count = 0;
                lastItem = null;
            } else {
                throw new IllegalStateException("You cannot delete that which doesn't exist. (No known item selected)");
            }
        }
    }
}
